iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 2
1
Software Development

LeetCode30系列 第 2

[LeetCode30] Day2 - 461. Hamming Distance

  • 分享至 

  • xImage
  •  

題目

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.
Note:
0 ≤ x, y < 231

Hamming distance

Hamming distance 就如同題目所說的,是兩個字串對應位置的不同字符的個數,在兩個數字來說就是指對應的位元。
一開始是在錯誤校正碼(ECC)中所提出的定義,現在也用於許多不同的地方。

1. 比較圖片相似程度

在建立一個圖片哈希搜索引擎,每張圖片都會經過hash function得到一串64位元的數字,因為這hash function保留了與原圖的關聯性,所以當2張圖越相似,則hamming distance會越小。
有興趣能參考這個:
https://www.pyimagesearch.com/2019/08/26/building-an-image-hashing-search-engine-with-vp-trees-and-opencv/

2. Flip-N-write (FNW)

相變記憶體(phash change memory)是一種非易失性記憶體,每個bit有一定的寫入次數,表示你一直覆寫,那個bit就很會快壞掉,不能再使用。
能想到的就是逐位比較,當原本就是0,要寫的又是0,就不要寫這個bit了。但有可能會發生很多bit都是不同的,都要寫入!!
FNW algorithm的主要想法就是在寫入新資料時,先與舊資料逐位比對,當超過半數不一樣(即Hamming distance大於資料位元數的一半),則會翻轉(flip)新資料,讓需要寫的bit變少(可控制在至少只要寫一半的bit),且只要用1個bit去紀錄是否有翻轉這件事。

解法

1.使用XOR

根據XOR的規則,兩數字經過XOR後,是1的位元就是兩數字相應bit不同的位置,那我只要在計算有多少個1,就能得到結果啦。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int xorRes = x ^ y;
        int hd = 0;
        while(xorRes > 0){
            hd += xorRes % 2;
            xorRes >>= 1;
        }
        return hd;
    }
};

2.不使用XOR

不用XOR 就只是各別提取x,y的對應位元再比較

class Solution {
public:
    int hammingDistance(int x, int y) {
        int hd = 0;
        while(x > 0 || y > 0) {
            hd += (x % 2 != y % 2) ? 1 : 0;
            x >>= 1;
            y >>= 1;
        }
        return hd;
    }
};

3. 標準函式庫

c++中有一個class叫做 bitset,能將給進去的值(如下為x^y),轉為給定位元數(如下為16)的2進制,並且有一個count功能,會回傳1的數量。

class Solution {
public:
    int hammingDistance(int x, int y) {
        bitset<32> xorRes(x^y);
        return xorRes.count();
    }
};

那基本上3種方法的結果都差不多,如下:
https://ithelp.ithome.com.tw/upload/images/20200917/20129147P7TJlloWWl.png


上一篇
[LeetCode30] Day1 - 前言 (還是有一題啦 顆顆)
下一篇
[LeetCode30] Day3 - 237. Delete Node in a Linked List
系列文
LeetCode3030
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言